package com.Offer;

import com.pojo.ListNode;

import java.util.List;

/*
    面试题25：合并两个排序的链表
    输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需 要合成后的链表满足单调不减规则。
 */
public class demo25 {
    public static void main(String[] args) {
        int[] input = new int[]{1,3,5,7};
        int[] input2 = new int[]{2,4,6,8};
        ListNode head1 = new ListNode(1);
        ListNode head2 = new ListNode(2);
        for(int i = 1;i<input.length;i++){
            head1.add(input[i]);
            head2.add(input2[i]);
        }
        ListNode res = combine2(head1,head2);
        while(res != null){
            System.out.print(res.val+" ");
            res = res.next;
        }

    }
    //递归
    public static ListNode combine(ListNode head1,ListNode head2){
        if(head1 == null){
            return head2;
        }
        if(head2 == null){
            return head1;
        }

        if(head1.val < head2.val){
            head1.next = combine(head1.next,head2);
            return head1;
        }else{
            head2.next = combine(head1,head2.next);
            return head2;
        }
    }

    //循坏迭代
    public static ListNode combine2(ListNode head1,ListNode head2){
        ListNode preHead = new ListNode(-1);
        ListNode pre = preHead;

        while (head1 != null && head2 != null){
            if(head1.val < head2.val){
                pre.next = head1;
                head1 = head1.next;
            }else{
                pre.next = head2;
                head2 = head2.next;
            }
            pre = pre.next;
        }
        pre.next = head1 == null ? head2 : head1;
        return preHead.next;
    }
}
